package binarySearch;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 进阶：
 * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
 *
 * 限制
 * 0 <= nums.length <= 10^5
 * -10^9<= nums[i]<= 10^9
 * nums是一个非递减数组
 * -10^9<= target<= 10^9
 *
 */
public class Find1stAnd2ndPosition_34 {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int[] res = new int[2];
        int left = 0;
        int right = nums.length - 1;
        // 搜索开始位置，整体搜索区间为[left, right]，注意是闭区间，之后的搜索区间都需要排除掉mid
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                // 不能直接返回，将搜索区间改为[left, mid-1]
                right = mid-1;
            } else if (nums[mid] < target) {
                // 将搜索区间改为 [mid+1, right]
                left = mid + 1;
            } else {
                // [left, mid-1]
                right = mid - 1;
            }
        }

        // 结束完循环之后，left必然大于right，但是也有可能超过数组长度，需要加以判断
        // 如果有开始位置，结束位置至少和开始位置相同，不必再判断
        if (left >= nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        } else {
            res[0] = left;
        }


        left = 0;
        right = nums.length - 1;
        // 搜索结束位置，整体搜索区间为[left, right]，注意是闭区间，之后的搜索区间都需要排除掉mid
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                // [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] < target) {
                // [mid+1, right]
                left = mid + 1;
            } else {
                // [left, mid-1]
                right = mid - 1;
            }
        }
        res[1] = right;
        return res;
    }
}
